package cn.dglydrpy.study.algorithm.od;

import java.util.ArrayList;
import java.util.Scanner;

/**
 * @author Yyy
 * @date 2024/11/10 11:50
 * @description  TODO
 * 充电站有 n 个充电设备，各有输出功率，任意组合的输出功率总和构成功率集合 P，
 * 要找到最接近充电站最大输出功率 p_max 的元素（即最优元素）
 */
public class Od0034_SubListSum {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNextLine()){

            int n = Integer.valueOf(scanner.nextLine());
            String[] s = scanner.nextLine().split(" ");
            ArrayList<Integer> list = new ArrayList<>();
            for(int i=0;i<n;i++){
                list.add(Integer.valueOf(s[i]));
            }
            
            int p_max = Integer.valueOf(scanner.nextLine());
            
            String ans = myAnswer(list,p_max);
            System.out.println(ans);
        }
    }

    private static String myAnswer(ArrayList<Integer> list,int p_max) {
        
        StringBuilder ans = new StringBuilder();
        if(list == null || list.isEmpty() || p_max == 0){
            return ans.toString();
        }

        boolean[] dp = new boolean[p_max + 1];
        // 初始化 dp[0] 为 true，表示总和为 0 是可以达到的（即不选任何设备）
        dp[0] = true;
        

        // 遍历每个充电设备的功率
        for (int power : list) {
            // 从最大输出功率开始递减遍历，避免重复计算已经确定的状态
            for (int i = p_max; i >= power; i--) {
                // 如果当前功率 i - power 可以达到，那么加上当前设备功率 power 后也可以达到
                dp[i] = dp[i] || dp[i - power];
            }
        }

        // 从最大输出功率开始递减遍历，找到第一个可以达到的功率，即为最优功率
        for (int i = p_max; i >= 0; i--) {
            if (dp[i]) {
                ans.append(i);
                break;
            }
        }
        
        return ans.toString();
    }
}
